The present invention relates generally to a square-root computation, and, more particularly, to a square-root computation embodied in a fixed-point processor or an Application Specific Integrated Circuit (ASIC).
In many real time applications, the square root operation serves as an xe2x80x9cinner loopxe2x80x9d operation, i.e. an operation called repeatedly as a subroutine by other subroutines of an application. Thus, the ultimate efficiency of a real time application is critically dependent on the efficiency of an underlying square root operation. In particular, this is true in audio signal processing and compression applications.
Computing the square root of any number can be a complicated and intensive computation. A fixed-point processor typically does not directly support this type of operation. That is, a fixed-point processor typically does not have a built-in instruction to compute a square root. If any application requires this function it must be implemented as an approximation in the software. The accuracy of the approximation depends significantly on the complexity of the calculations. Better approximations need more calculations and, conversely, more calculations produce better approximations.
A common technique for computing a square root operation is an iterative process called the Newton-Raphson technique. The Newton-Raphson technique is implemented using the following equation:
x(n+1)=xc2xd(x(n)+{fraction (xcex1/x(n))})
The number xe2x80x9caxe2x80x9d designates the number for which the square root is to be computed. The iterative process starts with n=0. The iterative process then proceeds with x(n+1) being calculated as a function of x(n) where n=1, 2, . . . N. The number of iteration cycles N needed to achieve an accurate approximation to the square root may be minimized by carefully choosing a start value. A well-chosen start value x(0) is typically stored in a predefined lookup-table.
The main problem with the Newton-Raphson technique is that a high computational load is needed to make the final result reliable. In many cases this technique is so computationally intensive, that further approximation must be done to make the calculation efficient. This will of course give an even more imprecise result. Another problem is that the look-up table occupies expensive memory area.
In view of the foregoing, it would be desirable to provide a technique which overcomes the above-described inadequacies and shortcomings. More particularly, it would be desirable to provide a technique for calculating the square root of a number in an efficient and cost effective manner.
According to the present invention, a technique for efficiently computing an approximation to the square root of a number X is provided. The number X is typically represented in a fixed-point binary form. In one embodiment, the technique can be realized by setting a first register of a processor to the number X. A second register of the processor is set to a number L, wherein the number L indicates a number of significant bits of X. The number L is right shifted in the second register by one bit to produce a number N. The number X is right shifted in the first register by N bits to produce a number X1. A third register of the processor is set to 1 and left shifted by N bits to produce the result N1 in the third register. The results N1 and X1 are added and shifted right by one bit to produce an approximation to the square root of X. Typically, the processor is a general purpose computer system, but may also be an Application Specific Integrated Circuit.